package hot100;

import java.util.*;

/**
 * @Author: wzp
 * @CreateTime: 2024-09-06  11:52
 * @Description: 字母异位词分组
 * @Version: 1.0
 */
public class hot_49 {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,List<String>> map=new HashMap<>();
        for (String str:strs){
            String key=getKey(str);
            map.putIfAbsent(key,new ArrayList<>());
            map.get(key).add(str);
        }
        return new ArrayList<>(map.values());
    }

    public String getKey(String str){
        char[] chars=str.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    public static void main(String[] args) {
//        s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
//        写个测试用例
        String s="catsandog";
        List<String> wordDict=new ArrayList<>();
        wordDict.add("cats");
        wordDict.add("dog");
        wordDict.add("sand");
        wordDict.add("and");
        wordDict.add("cat");
        System.out.println(new hot_49().wordBreak(s,wordDict));



    }
}
